package com.rw.tool.util.expression.expression;

import com.rw.tool.util.collection.CollectionUtil;
import com.rw.tool.util.expression.element.*;
import com.rw.tool.util.expression.exception.PostfixPrefixExpressionException;
import com.rw.tool.util.expression.expression.calculator.Calculator;
import com.rw.tool.util.expression.expression.tree.ElementNode;
import com.rw.tool.util.string.StringFormatter;

import java.math.BigDecimal;
import java.util.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

/**
 * 表达式
 */
public abstract class Expression {
    // 左括号正则表达式匹配
    public static final String LEFT_PARENTHESES_REGEX;

    // 右括号正则表达式匹配
    public static final String RIGHT_PARENTHESES_REGEX;

    // 运算符号正则表达式匹配
    public static final String CALCULATION_REGEX;

    static {
        // 从对应的元素中取出符号，并且组成正则表达式
        String leftRegex = LeftParentheses.LEFT.getSign()
                .stream()
                .map((Pattern::quote))
                .collect(Collectors.joining());

        String rightRegex = RightParentheses.RIGHT.getSign()
                .stream()
                .map((Pattern::quote))
                .collect(Collectors.joining());

        String calculationRegex = Calculation.getCalculationValues()
                .stream()
                .map(Sign::getSign)
                .flatMap(Collection::stream)
                .map(Pattern::quote)
                .collect(Collectors.joining());

        LEFT_PARENTHESES_REGEX = StringFormatter.format("[{}]", leftRegex);
        RIGHT_PARENTHESES_REGEX = StringFormatter.format("[{}]", rightRegex);
        CALCULATION_REGEX = StringFormatter.format("[{}]", calculationRegex);
    }

    // 表达式的元素
    private List<ExpressionElement> elements;

    public Expression(List<ExpressionElement> elements) {
        this.elements = elements;
    }

    protected Expression() {

    }

    /**
     * 计算表达式
     */
    public BigDecimal calculation() {
        ElementNode rootNode = getRootNode();
        return new Calculator().calculation(rootNode);
    }

    /**
     * 获得表达式根节点
     */
    public abstract ElementNode getRootNode();

    protected ElementNode getRootNode(List<ExpressionElement> expressionElements, boolean isPrefix) {
        List<ExpressionElement> elements = expressionElements;
        if (isPrefix) {
            elements = CollectionUtil.reverse(elements);
        }

        // 构造表达式树
        Stack<ElementNode> nodeStack = new Stack<>();
        for (ExpressionElement element : elements) {
            // 如果是数字，则直接入栈
            if (element instanceof NumberElement) {
                nodeStack.push(new ElementNode(element));
                continue;
            }

            // 如果不是数字，则连接两边的节点
            ElementNode rightNode = nodeStack.pop();
            ElementNode leftNode = nodeStack.pop();
            // 前缀表达式和后缀表达式的节点顺序不同
            if (isPrefix) {
                nodeStack.push(new ElementNode(element, rightNode, leftNode));
            } else {
                nodeStack.push(new ElementNode(element, leftNode, rightNode));
            }
        }
        return nodeStack.pop();
    }

    /**
     * 验证表达式是否合法，若不合法，则抛出异常
     */
    protected static void assertExpression(List<ExpressionElement> elements) {
        if (elements.stream().anyMatch(element -> element instanceof Parentheses)) {
            throw new PostfixPrefixExpressionException(elements);
        }

        // 数字元素的数量
        int numCount = 0;
        // 循环计数，为了抛出更加准确的异常信息
        int index = 0;
        for (ExpressionElement element : elements) {
            // 如果是数字元素，则增加计数
            if (element instanceof NumberElement) {
                numCount++;
                continue;
            }

            // 数字元素
            numCount -= 1;
            // 如果数字元素小于1，则抛出异常
            if (numCount < 1) {
                throw new PostfixPrefixExpressionException(elements, index);
            }

            // 循环计数加一
            index++;
        }
    }

    /**
     * 获取表达式的元素
     */
    public List<ExpressionElement> getElements() {
        return Collections.unmodifiableList(elements);
    }

    protected void setElements(List<ExpressionElement> elements) {
        this.elements = elements;
    }

    /**
     * 转化为中缀表达式
     */
    public InfixExpression toInfix() {
        return new InfixExpression(ToPrefixOrPostfix(this.getRootNode(), ExpressionType.INFIX));
    }

    /**
     * 转化为后缀表达式
     */
    public PostfixExpression toPostfix() {
        return new PostfixExpression(ToPrefixOrPostfix(this.getRootNode(), ExpressionType.POSTFIX));
    }

    /**
     * 转化为前缀表达式
     */
    public PrefixExpression toPrefix() {
        return new PrefixExpression(ToPrefixOrPostfix(this.getRootNode(), ExpressionType.PREFIX));
    }

    /**
     * 根据根节点，遍历出对应的表达式
     */
    private List<ExpressionElement> ToPrefixOrPostfix(ElementNode node, ExpressionType type) {
        List<ExpressionElement> result = new LinkedList<>();
        // 如果该节点没有子节点，直接返回
        if (node.isChild()) {
            result.add(node.getElement());
            return result;
        }

        // 根据不同的表达式，做出不同的遍历
        switch (type) {
            case PREFIX:
                // 前缀表达式前序遍历
                result.add(node.getElement());
                result.addAll(ToPrefixOrPostfix(node.getLeftNode(), type));
                result.addAll(ToPrefixOrPostfix(node.getRightNode(), type));
                break;
            case INFIX:
                // 中缀表达式中序遍历
                List<ExpressionElement> left = ToPrefixOrPostfix(node.getLeftNode(), type);
                List<ExpressionElement> right = ToPrefixOrPostfix(node.getRightNode(), type);

                // 如果左边的表达式优先度较低，则对左边的表达式加上括号
                if (getPriority(node.getLeftNode().getElement()) < getPriority(node.getElement())) {
                    addParentheses(left);
                }

                // 右边的表达式情况较为复杂一些
                if (shouldAddParentheses(node.getElement(), node.getRightNode().getElement())) {
                    addParentheses(right);
                }

                result.addAll(left);
                result.add(node.getElement());
                result.addAll(right);
                break;
            case POSTFIX:
                // 后缀表达式后序遍历
                result.addAll(ToPrefixOrPostfix(node.getLeftNode(), type));
                result.addAll(ToPrefixOrPostfix(node.getRightNode(), type));
                result.add(node.getElement());
                break;
        }
        return result;
    }

    /**
     * 判断是否需要加上括号
     */
    private boolean shouldAddParentheses(ExpressionElement element, ExpressionElement rightElements) {
        // 如果右边的节点就是子节点，则不需要加括号
        if (rightElements instanceof NumberElement) {
            return false;
        }

        // 如果右边的表达式优先度小于当前符号，则需要添加括号
        if (getPriority(rightElements) < getPriority(element)) {
            return true;
        }

        // 反之则不需要
        if (getPriority(rightElements) > getPriority(element)) {
            return false;
        }

        // 如果优先度相等，则取决于符号是否为符号或减号
        return element == Calculation.DIVISION || element == Calculation.MINUS;
    }

    /**
     * 给表达式两侧加上括号
     */
    private void addParentheses(List<ExpressionElement> elements) {
        elements.add(0, LeftParentheses.LEFT);
        elements.add(RightParentheses.RIGHT);
    }

    /**
     * 获取表达式元素的优先度
     */
    private int getPriority(ExpressionElement element) {
        // 如果不是运算符号，则优先度最高
        if (!(element instanceof Calculation)) {
            return 2;
        }
        return ((Calculation) element).getPriority();
    }

    @Override
    public String toString() {
        return getElements().stream()
                .map(Object::toString)
                .collect(Collectors.joining(" "));
    }
}
